package ninthweek;

import eighthweek.BinaryTreeADT;

public interface HeapADT<T> extends BinaryTreeADT<T> {
    /**
     * 添加元素操作，将给定的元素添加到堆的恰当位置处，且维持该堆的完全性属性和有序属性。
     * 如果该元素Comparable的，该方法将抛出一个ClassCastException异常。
     * @param obj
     * 关键概念：
     *  addElement方法将给定的Comparable元素添加到堆的恰当位置处，且维持该堆的完全属性和有序属性。
     *  因为一个堆是完全树，所以对插入新的结点而言 ，只存在一个正确的位置，且它要么是h层左边的下一个空位置，
     *  要么实在h+1层左边的第一个位置（如果h层是满层的话）。
     *  一旦将新结点定位到正确位置,就必须考虑排序属性。为此我们只需将该值与双亲值进行比较，如果新结点小于
     *  其双亲则将他们互换。我们沿着树向上继续这一过程，直至该新值要么是大于其双亲要么是位于该堆的根处。
     *
     */
    public void addElement(T obj);
    /**
     * removeMin方法将删除最小堆中的最小元素并返回它。由于最小元素是存储在最小堆的根处的，所以我们需要返回存储
     * 在根处的元素并用堆中的另一元素替换它，与addElement操作一样，要维持该树的完全性那么只有一个能替换根的合法
     * 元素，且它是存储在最末一片叶子上的元素。
     *
     * 一旦存储在最末一片叶子中的元素被移动到了根处，则必须对该堆进行重排序以维持该堆的排序属性。这一目标实现的方式，
     * 将该根元素与其较小的孩子进行比较，且如果孩子更小则将它们互换。 沿着树向下继续这一过程，直至该元素要么位于某一
     * 叶子中，要么比它的两个孩子都小。 显示了删除最小元素然后重新对树排序的过程。
     * @return
     */
    public T removeMin();
    /**
     * 返回一个指向该最小堆中的最小元素的引用。由于该元素总是存储在该树的根处，
     * 所以实现这一方法只需要通过返回存储根处的元素即可。
     * @return
     */
    public T findMin();

}
